#include <stdio.h>

int prime_table[1000050] = {0};
int range_table[1000050];

void prepare() {
    prime_table[0] = prime_table[1] = 1;
    for (int i = 2; i < 1050; i++) {
        for (int j = i * 2; j < 1000050; j += i) {
            prime_table[j] = 1;
        }
    }
    
    for (int i = 0, j = 0; i < 1000050; i++) {
        if (prime_table[i] == 0) {
            j++;
        }
        range_table[i] = j;
    }
}

int main(void) {
    prepare();
    int k;
    scanf("%d", &k);
    for (int i = 0; i < k; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        int min = a > b ? b : a;
        int max = a > b ? a : b;
        printf("%d\n", range_table[max] - range_table[min - 1]);
    }
    return 0;
}
